Computational Statistics
Table of Contents
1. Monte Carlo Method
2. Metropolis-Adjusted Langevin Algorithm
- MALA, Langevin Monte Carlo (LMC)
Given a probability distribution \( \pi \) on \( \mathbb{R}^d \), under the overdamped Langevin Itô diffusion \[ \dot{X} = \nabla \log \pi(X) + \sqrt{2} \dot{W}, \] \( f_{X_t}(x) \to \pi \) as \( t\to \infty \).
The approximate sample paths of the Langevin diffusion can be generated by many discrete-time methods. One of the simplest is the Euler-Maruyama method with a fixed time step \( \tau >0 \): \[ x_{k+1} := x_k + \tau \nabla \log \pi(x_k) + \sqrt{2\tau} \xi_k \] where \( \xi_k \) are independently drawn from a multivariate normal distribution with mean 0 and identity covariance matrix.
3. Kalman Filtering
Estimate the hidden state based on the indirect noisy observations.
It is a Markov chain with the state at each step being \( ( \mathbf{x}_k, \mathbf{P}_k, \mathbf{F}_k, \mathbf{H}_k, \mathbf{Q}_k, \mathbf{R}_k, \mathbf{B}_k, \mathbf{u}_k, \mathbf{z}_k )\), where
- \( \mathbf{x}_k \) is the true hidden state,
- \( \mathbf{P}_k \) is the predicted covariance of \( \mathbf{x}_k \),
- \( \mathbf{F}_k , \mathbf{B}_k, \mathbf{u}_k\) are the state-transition model, control-input model, and control vector that determine the hidden state: \[ \mathbf{x}_k = \mathbf{F}_k \mathbf{x}_{k-1} + \mathbf{B}_{k}\mathbf{u}_k + \mathbf{w}_k \] with process noise \( \mathbf{w}_k \) being a sample from the zero mean multivariate normal distribution with covariance \( \mathbf{Q}_{k} \),
- \( \mathbf{H}_k \) is the observation model that outputs the observation \( \mathbf{z}_k \) \[ \mathbf{z}_k = \mathbf{H}_k\mathbf{x}_k + \mathbf{v}_k \] with observation noise \( \mathbf{v}_k \) sampled from the zero mean multivariate normal with covariance \( \mathbf{R}_{k} \)
4. Resampling
4.1. Importance Sampling
4.1.1. Method
When calculating the average by the Monte Carlo method: \[ \mathrm{E}_p[f(X)] = \int_\Omega f(\mathbf{x})p(\mathbf{x})\,d\mathbf{x} \approx \frac{1}{N}\sum_{i=1}^N f(\mathbf{x}_i),\ \mathbf{x}_i \sim p(\mathbf{x}) \] We might be able to reduce the variance with \(q(\mathbf{x})\) that is high when \(|f(\mathbf{x})p(\mathbf{x})|\) is high: \[ \mathrm{E}_p[f(\mathbf{x})] = \mathrm{E}_q\left[\frac{p(\mathbf{x})}{q(\mathbf{x})}f(\mathbf{x})\right] \approx \frac{1}{N}\sum_{i=1}^N \frac{p(\mathbf{x}_i)}{q(\mathbf{x}_i)}f(\mathbf{x}_i),\ \mathbf{x}_i \sim q(\mathbf{x}). \]
4.1.2. Conditions
- \(p(\mathbf{x})\) is difficult to sample from
- We can evaluate \(p(\mathbf{x})\)
- \(q(\mathbf{x})\) is easy to evaluate and sample from
- We can choose \(q(\mathbf{x})\) to be high where \(|p(\mathbf{x})f(\mathbf{x})|\) is high.
4.2. Bootstrapping
The population mean \(\mu\) can be estimated by the sample mean \(\hat{\mu}=\bar{X}\). To make a decision we need to know the distibution of the sample mean on top of that.
The cumulative probability distribution \(F_n\) of the sample mean can then be estimated by the bootstrap distribution \(\hat{F}_n\), which can be used to estimate the statistics of the sample mean such as the mean \(\widehat{\mathrm{E}[\bar{X}]}\) and other stuffs.
Bootstrap distribution can be obtained by empirically computing all the possible combinations of the samples. But since the possible resampling are two many in practice we then use the Monte Carlo method \(\bar{F}_n\) on the bootstrap distribution \(\hat{F}_n\).
4.3. Permutation Tests
Data is resampled with the underlying true values permuted in everyway.